package william.array;


/**
 * @author ZhangShenao
 * @date 2024/2/29
 * @description <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/">...</a>
 */
public class Leetcode26_删除有序数组中的重复项 {
    /**
     * 采用双指针法
     * 指针i用于遍历数组
     * 指针lastNonDup用于记录最后一个不重复的元素的位置,[0,lastNonDup)范围内的元素均不重复,lastNonDup初始=1
     * 从下标1开始遍历数组,如果当前元素与lastNonDup的前一个元素不相等,则将lastNonDup位置的元素赋值为当前元素,并将lastNonDup+1
     * 最终返回lastNonDup即为不重复元素的数组长度
     * 时间复杂度O(N) 仅遍历一次数组
     * 空间复杂度O(1)
     */
    public int removeDuplicates(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return 0;
        }

        //采用双指针
        //指针i用于遍历数组
        //指针lastNonDup用于记录最后一个不重复的元素的位置,[0,lastNonDup)范围内的元素均不重复
        int lastNonDup = 1;

        //从下标1开始遍历数组
        for (int i = 1; i < nums.length; i++) {
            //当前元素与lastNonDup的前一个元素不相等,则将当前元素赋值到lastNonDup位置,并将lastNonDup+1
            if (nums[i] != nums[lastNonDup - 1]) {
                nums[lastNonDup++] = nums[i];
            }
        }

        //最终lastNonDup即为不重复元素的数量,直接返回
        return lastNonDup;
    }

}
